package com.xw.class03;

/**
 * @author: xw
 * @create: 2022/9/8 17:50
 * @description: 用双链表模拟栈和队列
 */
public class Code03_DoubleEndsQueueToStackAndQueue {
    public static class Node<T> {
        public T value;
        public Node<T> last;
        public Node<T> next;

        public Node(T data) {
            value = data;
        }
    }

    public static class DoubleEndsQueue<T> {
        public Node<T> head;
        public Node<T> tail;

        public void addFromHead(T value) {
            Node<T> cur = new Node<T>(value);
            if(null == head){
                head = cur;
                tail = cur;
            }else{
                cur.next = head;
                head.last = cur;
                head = cur;
            }
        }
        public void addFromBottom(T value) {
            Node<T> cur = new Node<T>(value);
            if(null == head){
                head = cur;
                tail = cur;
            }else{
                tail.next = cur;
                cur.last = tail;
                tail = cur;
            }
        }

        public T popFromHead() {
            if(null ==  head){
                return null;
            }
            Node<T> cur = head;
            if(head == tail){
                head = null;
                tail = null;
            }else{
                head = head.next;
                cur.next = null;
                head.last = null;
            }
            return cur.value;
        }
        public T popFromBottom() {
            if(null == head){
                return null;
            }
            Node<T> cur = tail;
            if(head == tail){
                head = null;
                tail = null;
            }else{
                tail = tail.last;
                tail.next = null;
                cur.last = null;
            }
            return cur.value;
        }
        public boolean isEmpty() {
            return head == null;
        }
    }

    public static class MyStack<T> {
        private DoubleEndsQueue<T> queue;

        public MyStack() {
            queue = new DoubleEndsQueue<T>();
        }

        public void push(T value) {
            queue.addFromHead(value);
        }

        public T pop() {
            return queue.popFromHead();
        }

        public boolean isEmpty() {
            return queue.isEmpty();
        }
    }

    public static class MyQueue<T> {
        private DoubleEndsQueue<T> queue;

        public MyQueue() {
            queue = new DoubleEndsQueue<T>();
        }

        public void push(T value) {
            queue.addFromHead(value);
        }

        public T poll() {
            return queue.popFromBottom();
        }

        public boolean isEmpty() {
            return queue.isEmpty();
        }

    }
}
